题解 CF538F 【A Heap of Heaps】

发表于 | 更新于

神仙题

题意：给一个数组建完全$k$叉树，$k$范围$[1,n-1]$，问每个$k$对应的不满足最小堆性质的结点个数

暴力$n^2$肯定要$T$飞，这里先引入几个性质：

$1.\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+…+\frac{n}{n-1}+\frac{n}{n}=nlogn$(调和级数)

2.在$i$叉树中，一个节点$j$的儿子的范围一定是一段区间$(j×i-i+2)$~$(j×i+1)$

接下来是正解，我们发现对于一个节点$x$，它儿子中所有不合法的节点数即是它儿子中权值小于$x$的权值的数量，这显然可以联想到树状数组求逆序对的思想。

先排一遍序，记录下第i小的数在原先序列中的位置。然后从小的数开始处理，小的数后面肯定是大的数，不可能会出现非法节点，然后处理完小的数之后维护树状数组，对小的数对应的权值单点修改$+1$，这样在后面处理大的数的时候询问就会算上这些更新后的权值了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define lowbit(x) (x&-x) 
using namespace std;
struct node{
    int a,b;
}a[400000];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int n,c[400000],ans[400000];
inline bool cmp(node a,node b){
    if (a.a!=b.a)return a.a<b.a;
    else return a.b<b.b;
}
inline void change(int x){
    for (;x<=n;x+=lowbit(x))
        ++c[x];
}
inline int sum(int x){
    int res=0;
    for (;x;x-=lowbit(x))
        res+=c[x];
    return res;
}
int main(){
    n=read();
    for (int i=1;i<=n;++i)
        a[i].a=read(),a[i].b=i;
    sort(a+1,a+1+n,cmp);
    for (int i=1;i<=n;++i){
        change(a[i].b);
        for (int j=1;j<n&&a[i].b*j-j+2<=n;++j)
            ans[j]+=sum(min(n,a[i].b*j+1))-sum(a[i].b*j-j+1);
    }
    for (int i=1;i<n;++i)printf("%d ",ans[i]);
}